package geek;

import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * @author sam
 * 2021/10/20 22:17
 * @description
 * @editor
 * @description
 * Two Sum
 * Three Sum
 *
 * 两数之和
 *
 * [2,7,11,15]  两数和为9 返回下标
 * return
 * [0,1]
 */
public class Lesson15 {

    /*
    暴力
    [x，y]=> x+y=9
     */
    @Test
    public void twoSumTest(){
       System.out.println(Arrays.toString(twoSum(new int[]{1,4,2, 6,7, 11, 15},9)));
       System.out.println(Arrays.toString(twoSumSet(new int[]{1,4,2, 6,7, 11, 15},9)));
    }

    private int[] twoSum(int[] nums,int sum){
        int[] result = new int[2];
        for (int i = 0; i < nums.length; i++) {
            for (int i1 = nums.length-1; i1 >0; i1--) {
                if (i<i1) {
                    if (nums[i] + nums[i1] == sum) {
                        result[0] = i;
                        result[1] = i1;
                    }
                }
            }
        }
        return result;
    }

    /*
    Set:
     */
    private int[] twoSumSet(int[] nums,int sum){
        int[] result = new int[2];
        Map<Integer,Integer> integers = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
           if (integers.containsKey(sum-nums[i])){
               result[0] = integers.get(sum-nums[i]);
               result[1] = i;
           }else {
               integers.put(nums[i],i);
           }
        }
        return result;
    }
}
